class code3 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int ret = Integer.MAX_VALUE;
        int sz = triangle.size();
        int[] dp = new int[sz];

        dp[0] = triangle.get(0).get(0);

        int prev = 0;//暂存dp[i-1][j-1]
        int cur = 0;//暂存dp[i-1][j]

        for(int i=1;i<sz;i++) {
            for(int j=0;j<=i;j++) {
                cur = dp[j];
                if(j==0) {
                    dp[j] = cur + triangle.get(i).get(j);
                } else if(j == i) {
                    dp[j] = prev + triangle.get(i).get(j);
                } else {
                    dp[j] = Math.min(cur,prev) + triangle.get(i).get(j);
                }
                prev = cur;
            }
        }

        for(int i=0;i<sz;i++) {
            ret = Math.min(ret,dp[i]);
        }

        return ret;
    }
}